Parameterized approximation of dominating set problems

Title: Parameterized approximation of dominating set problems
Creator: Downey, Rodney G.; Fellows, Michael R.; McCartin, Catherine; Rosamond, Frances
Relation: Information Processing Letters Vol. 109, Issue 1, p. 68-70
Publisher Link: http://dx.doi.org/10.1016/j.ipl.2008.09.017
Publisher: Elsevier
Resource Type: journal article
Date: 2008
Description: A problem open for many years is whether there is an FPT algorithm that given a graph G and parameter k, either: (1) determines that G has no k-Dominating Set, or (2) produces a dominating set of size at most g(k), where g(k) is some fixed function of k. Such an outcome is termed an FPT approximation algorithm. We describe some results that begin to provide some answers. We show that there is no such FPT algorithm for g(k) of the form k+c (where c is a fixed constant, termed an additive FPT approximation), unless FPT = W[2]. We answer the analogous problem completely for the related Independent Dominating Set (IDS) problem, showing that IDS does not admit an FPT approximation algorithm, for any g(k), unless FPT = W[2].
Subject: parameterized complexity; FPT approximation; approximation algorithms
Identifier: http://hdl.handle.net/1959.13/43088
Identifier: uon:5217
Identifier: ISSN:0020-0190
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format